// 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

// 进阶：

// 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

// 输入：head = [-1,5,3,4,0]
// 输出：[-1,0,3,4,5]

//对链表进行归并排序，代码思路清晰
class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode middle = middleNode(head);
        ListNode righthead = middle.next;
        middle.next = null;
        ListNode left =sortList(head);
        ListNode right =sortList(righthead);
        ListNode result = SortNode(left,right);
        return result;
    }
    public ListNode middleNode(ListNode node){
        if(node == null||node.next == null)
            return node;
        ListNode src = node;
        ListNode cur = node.next.next;
        while(cur!=null&&cur.next!=null)
        {
            src = src.next;
            cur = cur.next.next;
        }
        return src;
    }
    public ListNode SortNode(ListNode l1,ListNode l2){
        ListNode src = new ListNode(-1);
        ListNode cur = src;
        while(l1!=null&&l2!=null)
        {
            if(l1.val<l2.val)
            {
                cur.next = l1;
                l1 = l1.next;
            }
            else{
                cur.next=l2;
                l2=l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1==null?l2:l1;
        return src.next;
    }
}